public class Test {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int ret;
        int[] nums = new int[]{1,3,5,6};
        ret = solution.searchInsert(nums,2);
        System.out.println(ret);
    }
}

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length-1;
        while(left < right){
            //
            int mid = left + (right - left)/2;
            if(nums[mid] < target){
                left = mid + 1;
            }else{
                right = mid;
            }


            //另一种移动方案：（二分策略）
            /*int mid = left + (right - left +1)/2;
            if(nums[mid] <= target){
                left = mid;
            }else{
                right = mid - 1;
            }*/
        }
        if(nums[left] == target){
            return left;
        }else if(nums[left] > target){
            return left ;
        }else {
            return left + 1;
        }

    }
}
